// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-27 14:18
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Greedy;

public class JumpByGreedyT {
    // 优化贪心算法
    public int jump(int[] nums) {
        // 使用边界值定位
        int maxPosition = nums[0];
        int step = 0;
        int end = 0; // 用于重新定位position
        for (int i = 0; i < nums.length - 1; i++) { // 当到达数组尾时候已经结束，无需再增加多余步数
            maxPosition = Math.max(maxPosition, nums[i] + i); // 获取局部最大步数
            if (i == end) {
                end = maxPosition;
                ++step;
            }
        }
        return step;

    }
}
